- Title
- Circumcentering Reflection Methods for Nonconvex Feasibility Problems
- Creator
- Dizon, Neil D.; Hogan, Jeffrey A.; Lindstrom, Scott B.
- Relation
- ARC.DP160101537 http://purl.org/au-research/grants/arc/DP160101537
- Relation
- Set-Valued and Variational Analysis Vol. 30, Issue 3, p. 943-973
- Publisher Link
- http://dx.doi.org/10.1007/s11228-021-00626-9
- Publisher
- Springer
- Resource Type
- journal article
- Date
- 2022
- Description
- Recently, circumcentering reflection method (CRM) has been introduced for solving the feasibility problem of finding a point in the intersection of closed constraint sets. It is closely related with Douglas–Rachford method (DR). We prove local convergence of CRM in the same prototypical settings of most theoretical analysis of regular nonconvex DR, whose consideration is made natural by the geometry of the phase retrieval problem. For the purpose, we show that CRM is related to the method of subgradient projections. For many cases when DR is known to converge to a feasible point, we establish that CRM locally provides a better convergence rate. As a root finder, we show that CRM has local convergence whenever Newton–Raphson method does, has quadratic rate whenever Newton–Raphson method does, and exhibits superlinear convergence in many cases when Newton–Raphson method fails to converge at all. We also obtain explicit regions of convergence. As an interesting aside, we demonstrate local convergence of CRM to feasible points in cases when DR converges to fixed points that are not feasible. We demonstrate an extension in higher dimensions, and use it to obtain convergence rate guarantees for sphere and subspace feasibility problems. Armed with these guarantees, we experimentally discover that CRM is highly sensitive to compounding numerical error that may cause it to achieve worse rates than those guaranteed by theory. We then introduce a numerical modification that enables CRM to achieve the theoretically guaranteed rates. Any future works that study CRM for product space formulations of feasibility problems should take note of this sensitivity and account for it in numerical implementations.
- Subject
- douglas–rachford; feasibility; projection methods; reflection methods; iterative methods; circumcentering
- Identifier
- http://hdl.handle.net/1959.13/1473810
- Identifier
- uon:49115
- Identifier
- ISSN:1877-0533
- Rights
- This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
- Language
- eng
- Full Text
- Reviewed
- Hits: 854
- Visitors: 871
- Downloads: 35
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT02 | Publisher version (open access) | 1 MB | Adobe Acrobat PDF | View Details Download |